package 二分算法;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/contains-duplicate-ii/description/
 * 重复元素II
 */
public class likou219 {

    // 暴力枚举: O(n ^ 2)  哈希表: O(n)
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // int[] hash = new int[100000];
        // key 是值, value 是下标
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 先判断是不是重复的, 然后进行比较
            if(hash.containsKey(nums[i])) {
                // 如果不成立, 则需要更改位置为靠后的, 有一个小贪心.
                if(i - hash.get(nums[i]) <= k) return true;
                else hash.put(nums[i], i);

            }else {
                hash.put(nums[i], i);
            }
        }
        return false;
    }

}
